from typing import List, Optional


# 95. 不同的二叉搜索树 II
# https://leetcode.cn/problems/unique-binary-search-trees-ii/

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def gen(start, end):
            if start > end:
                return [None]
            
            trees = []
            for i in range(start, end+1):
                left = gen(start, i-1)
                right = gen(i+1, end)

                for l in left:
                    for r in right:
                        node = TreeNode(val=i, left=l, right=r)
                        trees.append(node)
            
            return trees

        return gen(1, n) if n else []
